package org.example;

public class Strings {
    // 151. 反转字符串中的单词
    // 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
    // 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
    // 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
    // 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
    // 示例 1：
    // 输入：s = "the sky is blue"
    // 输出："blue is sky the"
    static class ReverseWords {
        // 双指针（时间复杂度O(N)）
        // 思路：
        // 倒序遍历字符串s，记录单词左右索引边界i，j。
        // 每确定一个单词的边界，则将其添加至单词列表res。
        // 最终，将单词列表拼接为字符串，并返回。
        public String reverseWords(String s) {
            s = s.trim(); // 删除首尾字母
            int j = s.length() - 1;
            int i = s.length() - 1;
            StringBuilder res = new StringBuilder();
            while (i >= 0) {
                while (i >= 0 && s.charAt(i) != ' ') { // 搜索首个空格
                    i--;
                }
                res.append(s, i + 1, j + 1).append(" "); // 添加单词
                while (i >= 0 && s.charAt(i) == ' ') { // 跳过单词间空格
                    i--;
                    j = i; // j 指向下个单词的尾字符
                }
            }
            return res.toString().trim(); // 转化为字符串并返回
        }
    }
}
